#include <vector>
#include <iostream>
#include <unordered_map>
#include <numeric>

using namespace std;

// 使用时间过长
class mySolution {
public:
    static bool isAnagram(string s, string t) {
        vector<int> num(122-97+1, 0);
        if(s.size() != t.size()){ return false; }
        for(int i = 0; i < s.size(); i++){
            num[int(s[i])-97]++;
        }
        for(int i = 0; i < t.size(); i++){
            if(--num[int(t[i])-97] == -1){
                return false;
            }
        }
        return true;
    }

    static vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        while(strs.size() > 0){
            vector<string> same = { strs[0] };
            for(int j = 1; j < strs.size(); j++){
                if(isAnagram(strs[0], strs[j])){
                    same.push_back(strs[j]);
                    strs.erase(strs.begin() + j--);
                }
            }
            strs.erase(strs.begin());
            ret.push_back(same);
        }
        return ret;
    }
};

class Solution {
public:
    static vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 无序唯一关键字-值对（关键字：字符串；值：字符串数组）
        unordered_map<string, vector<string>> mp;
        // 把字符串的字母按顺序排列，并设为关键字
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            // emplace()是头插入，而emplace_back()是尾插入
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }

    // vector<vector<string>> groupAnagrams(vector<string>& strs) {
    //     // 自定义对 array<int, 26> 类型的哈希函数
    //     auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
    //         return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
    //             return (acc << 1) ^ fn(num);
    //         });
    //     };

    //     unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
    //     for (string& str: strs) {
    //         array<int, 26> counts{};
    //         int length = str.length();
    //         for (int i = 0; i < length; ++i) {
    //             counts[str[i] - 'a'] ++;
    //         }
    //         mp[counts].emplace_back(str);
    //     }
    //     vector<vector<string>> ans;
    //     for (auto it = mp.begin(); it != mp.end(); ++it) {
    //         ans.emplace_back(it->second);
    //     }
    //     return ans;
    // }
};

int main(){
    vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> ret = Solution::groupAnagrams(strs);
    for(int i = 0; i < ret.size(); i++){
        for(int j = 0; j < ret[i].size(); j++){
            cout << ret[i][j] + " ";
        }
        cout << endl;
    }
    return 0;
}